#include <bits/stdc++.h>

using namespace std;

// 二叉搜索子树的最大键值和
// 给你一棵以 root 为根的二叉树
// 请你返回 任意 二叉搜索子树的最大键值和
// 二叉搜索树的定义如下：
// 任意节点的左子树中的键值都 小于 此节点的键值
// 任意节点的右子树中的键值都 大于 此节点的键值
// 任意节点的左子树和右子树都是二叉搜索树
// 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    struct Info
    {
        // 为什么这里的mx和mn是int类型？
		// 因为题目的数据量规定，
		// 节点值在[-4 * 10^4，4 * 10^4]范围
		// 所以int类型的最小值和最大值就够用了
		// 不需要用long类型
        int mx, mn, sum;
        bool isBst;
        int maxBstSum;

        Info(int a, int b, int c, bool d, int e)
            : mx(a), mn(b), sum(c)
            , isBst(d), maxBstSum(e)
        {}
    
    };

    Info f(TreeNode* x)
    {
        if(x == nullptr) return Info(INT_MIN, INT_MAX, 0, true, 0);

        Info&& leftInfo = f(x->left);
        Info&& rightInfo = f(x->right);
        int mx = max(x->val, max(leftInfo.mx, rightInfo.mx));
        int mn = min(x->val, min(leftInfo.mn, rightInfo.mn));
        int sum = leftInfo.sum + rightInfo.sum + x->val;
        bool isBst = leftInfo.isBst && rightInfo.isBst && x->val > leftInfo.mx && x->val < rightInfo.mn;
        int maxBstSum = max(leftInfo.maxBstSum, rightInfo.maxBstSum);
        if(isBst) maxBstSum = max(maxBstSum, sum);

        return Info(mx, mn, sum, isBst, maxBstSum); 
    }

public:
    int maxSumBST(TreeNode* root) 
    {
        return f(root).maxBstSum;
    }
};